package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第318场单周赛 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(applyOperations(new int[]{0, 1})));

        System.out.println(maximumSubarraySum(new int[]{5, 3, 3, 1, 1}, 3));

        System.out.println(totalCost(new int[]{57, 33, 26, 76, 14, 67, 24, 90, 72, 37, 30}, 11, 2));

    }

    /**
     * 模拟
     *
     * @param nums
     * @return
     */
    public static int[] applyOperations(int[] nums) {
        int[] ans = new int[nums.length];
        int idx = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) {
                continue;
            }
            if (nums[i] == nums[i + 1]) {
                ans[idx] = nums[i] * 2;
                nums[i + 1] = 0;
                i++;

            } else {
                ans[idx] = nums[i];
            }
            idx++;
        }
        ans[idx] = nums[nums.length - 1];

        return ans;
    }

    /**
     * 滑动窗口
     *
     * @param nums
     * @param k
     * @return
     */
    public static long maximumSubarraySum(int[] nums, int k) {
        long sum = 0;
        Set<Integer> set = new HashSet<>();
        Deque<Integer> queue = new ArrayDeque<>();

        long curSum = 0;
        for (int i = 0; i < nums.length; ) {
            while (i < nums.length && set.size() < k) {
                if (set.add(nums[i])) {
                    queue.addLast(nums[i]);
                    curSum += nums[i];
                } else {
                    set = new HashSet<>();
                    queue = new ArrayDeque<>();
                    curSum = 0;

                    set.add(nums[i]);
                    queue.addLast(nums[i]);
                    curSum += nums[i];
                }
                i++;
            }

            if (set.size() == k) {
                sum = Math.max(sum, curSum);
            }
            Integer sub = queue.pollFirst();
            set.remove(sub);
            curSum -= sub;
        }

        return sum;
    }

    /**
     * 6231. 雇佣 K 位工人的总代价 显示英文描述
     * 优先队列
     * 如果对于前半部分，或者后半部分优先队列内部，索引是没有意义的，
     * 优先选择较小的数字即可
     * 如果前半部分的最小数字等于后半部分的最小数字，选择索引较小部分
     * 的花费，也就是优先选择前半部分的花费
     * 其他情况，优先选择 前后部分 较小的那个花费就行
     */
    public static long totalCost(int[] costs, int k, int candidates) {
        long minCost = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int cost : costs) {
            queue.addLast(cost);
        }
        PriorityQueue<Integer> head = new PriorityQueue<>((a, b) -> a - b);
        PriorityQueue<Integer> tail = new PriorityQueue<>((a, b) -> a - b);

        while (k-- > 0) {
            while (!queue.isEmpty() && head.size() < candidates) {
                head.add(queue.pollFirst());
            }
            while (!queue.isEmpty() && tail.size() < candidates) {
                tail.add(queue.pollLast());
            }

            if (tail.isEmpty()) {
                minCost += head.poll();
                continue;
            }
            if (head.isEmpty()) {
                minCost += tail.poll();
                continue;
            }

            if (head.peek() <= tail.peek()) {
                minCost += head.poll();
            } else {
                minCost += tail.poll();
            }
        }

        return minCost;
    }

}
